package demo16;

import demo1.LinkList;
import demo11.Tree;

import java.util.*;

public class Tree44 {
    static class TreeNode44 {
        public char val;
        public TreeNode44 left;
        public TreeNode44 right;

        public TreeNode44(char val) {
            this.val = val;
        }
    }
    public TreeNode44 create4()
    {
        TreeNode44 head=new TreeNode44('A');
        TreeNode44 head2=new TreeNode44('B');
        TreeNode44 head3=new TreeNode44('C');
        TreeNode44 head4=new TreeNode44('D');
        TreeNode44 head5=new TreeNode44('E');
        TreeNode44 head6=new TreeNode44('F');
        head.left=head2;
        head.right=head3;
        head2.left=head4;
        head2.right=head5;
        head3.left=head6;
        return head;
    }
    //利用队列实现层序遍历
        public void levelorder(TreeNode44 head) {
            if(head==null){
                System.out.println("树为空！");
                return;
            }
            TreeNode44 cur=head;
            Queue<TreeNode44> q=new LinkedList();
            q.offer(cur);
            while(!q.isEmpty()){
                TreeNode44 cur1=q.poll();//弹出队中元素并打印
                System.out.print(cur1.val+" ");
                if(cur1.left!=null){ //节点左右不为空左右存入队里
                    q.offer(cur1.left);
                }
                if(cur1.right!=null){
                    q.offer(cur1.right);
                }
            }
        }
    //计算节点个数
    public int size;
    public int size(TreeNode44 head){
        if(head==null){
            return 0;
        }
        size++;
        size(head.left);
        size(head.right);
        return size;
    }
    //队列实现层序遍历
    public List<List<Character>> linkorder(TreeNode44 head){

        List<List<Character>> ret=new ArrayList<>();
        if(head==null){
            return ret;
        }
        Queue<TreeNode44> q=new LinkedList<>();
        q.offer(head);
        int size=size(head);
        while(!q.isEmpty()) {
            List <Character>list= new ArrayList<>();
            while (size != 0) {
                TreeNode44 cur = q.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
            return ret;
        }
        //利用队列层序遍历判断一棵树是否是完全二叉树
    public boolean isComp (TreeNode44 head){
        if(head==null){
            return true;
        }
        Queue<TreeNode44> q=new LinkedList<>() ;
        q.offer(head);
        while(!q.isEmpty()){
            TreeNode44 cur=q.poll();
            if(cur!=null){
                q.offer(cur.left);
                q.offer(cur.right);
            }else{
                break;
            }

        }
        while(!q.isEmpty()){
            TreeNode44 peek=q.peek();
            if(peek!=null){
                return false;
            }
            q.poll();
        }
        return true;
    }
    //给定一棵二叉树找到该树两个指定节点的共同祖先
    public TreeNode44 lowest(TreeNode44 head,TreeNode44 p,TreeNode44 q){
        if(head==null){
            return head;
        }
        if(head==p||head==q){
            return head;
        }
        TreeNode44 l=lowest(head.left, p, q);
        TreeNode44 r=lowest(head.right, p, q);
        if(l!=null&&r!=null){
            return head;
        } else if (l!=null) {
            return l;
        }else{
            return r;
        }
    }
    //寻找两个节点的最近的公共祖先的节点
    public boolean getPath(TreeNode44 head, TreeNode44 node, Stack<TreeNode44> stack){//先在树中找到节点
        if(head==null){
            return false;
        }
        stack.push(head);
        if(head==node){
            return true;
        }
        boolean ret=getPath(head.left,node,stack);
        if(ret){
            return true;
        }
        boolean ret2=getPath(head.right,node,stack);
        if(ret2){
            return true;
        }
        stack.pop();//左右子树都没找到目标节点，说明当前节点不在从根到目标节点的路径上，将其从栈中弹回，保证只保留有效路径的节点
        return false;
    }
    public TreeNode44 deal(TreeNode44 head,TreeNode44 p,TreeNode44 q) {
        if (head == null) {
            return null;
        }
        Stack<TreeNode44> stack1 = new Stack<>();
        Stack<TreeNode44> stack2 = new Stack<>();
        if (!getPath(head, p, stack1) || !getPath(head, q, stack2)) {
            return null;
        }
        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                stack1.pop();//去除多余路径
                size--;
            }
        } else {
            int size = size2 - size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek().equals(stack2.peek())) {//两个栈同时弹出找到相同的节点时返回
                return stack1.peek();
            }
            stack1.pop();
            stack2.pop();
        }
        return null;
    }
    }
